class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = cost.size();

        for (int i = 0; i < n; ++i)
        {
            int sum = 0;

            //枚举环
            //step为从i开始，走n步
            //越界就对数组长度取模
            for (int step = 0; step < n; ++step)
            {
                int index = (i + step) % n;
                sum += gas[index] - cost[index];
                if (sum < 0)
                {
                    //对于diff数组，diff = gas - cost
                    //如果 a + b + c + d + e + f < 0
                    //因为 a如果可以走到b，说明a > 0
                    //则   b + c + d + e + f < 0
                    //....
                    //即 如果a走到f后，走不动了，那么a到f中间的就不需要考虑，也一定走不动
                    //直接将起点跳到f+1即可
                    i = i + step;   //优化
                    break;
                }
            }
            if (sum >= 0)
                return i;
        }
        
        return -1;
    }
};


class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> counts(n, 1);
        
        //从左往右模拟一遍
        for (int i = 1; i < n; ++i)
            if (ratings[i] > ratings[i - 1])
                counts[i] = counts[i - 1] + 1;

        //从右往左模拟一遍
        for (int i = n - 2; i >= 0; --i)
            if (ratings[i] > ratings[i + 1]) 
                counts[i] = max(counts[i + 1] + 1, counts[i]);

        return accumulate(counts.begin(), counts.end(), 0);
    }
};

class Solution {
public:
    int trap(vector<int>& height) {
        int left = 1, right = height.size() - 2;
        int left_max_high = height.front(), right_max_high = height.back();
        int total = 0;

        while (left <= right)
        {
            if (left_max_high < right_max_high)
            {
                total += max(0, left_max_high - height[left]);
                left_max_high = max(left_max_high, height[left]);
                ++left;
            }
            else
            {
                total += max(0, right_max_high - height[right]);
                right_max_high = max(right_max_high, height[right]);
                --right;
            }
        }

        return total;
    }
};